package com.leetcode.No0813;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * @program: Solution
 * @description: 最大平均值和的分组
 *      dp
 * @author: Wang Zhihua
 * @date: 2022-11-28
 */
public class Solution2 {

    public double largestSumOfAverages(int[] nums, int k) {
        int len = nums.length;
        double[][] dp = new double[len + 1][k + 1];
        double[] prefixSum = new double[len + 1];
        for (int i = 1; i <= len; ++i) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= len; ++i) {
            dp[i][1] = prefixSum[i] / i;
        }
        for (int j = 2; j <= k; ++j) {
            for (int i = j; i <= len; ++i) {
                for (int x = j - 1; x < i; ++x) {
                    double sum = prefixSum[i] - prefixSum[x];
                    dp[i][j] = Math.max(dp[i][j], dp[x][j - 1] + (sum / (i - x)));
                }
            }
        }
        return dp[len][k];
    }

    @Test
    public void test01() {
        int[] nums;
        int k;

        nums = new int[]{9,1,2,3,9};
        k = 3;
        System.out.println(new Solution2().largestSumOfAverages(nums, k));

        nums = new int[]{1,2,3,4,5,6,7};
        k = 4;
        System.out.println(new Solution2().largestSumOfAverages(nums, k));

        nums = new int[]{4663,3020,7789,1627,9668,1356,4207,1133,8765,4649,205,6455,8864,3554,3916,5925,3995,4540,3487,5444,8259,8802,6777,7306,989,4958,2921,8155,4922,2469,6923,776,9777,1796,708,786,3158,7369,8715,2136,2510,3739,6411,7996,6211,8282,4805,236,1489,7698};
        k = 27;
        System.out.println(new Solution2().largestSumOfAverages(nums, k));
    }
}
